package 数据结构练习.summer;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

public class day13 {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {
        }
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    /*
    给你单链表的头节点 head ，请你反转链表，并返回反转后的链表
    https://leetcode.cn/problems/reverse-linked-list/description/
     */
    public ListNode reverseList(ListNode head) {
        //先将所有的元素存入栈然后再弹出重新组成链表最后一个元素的next记得赋值null
        Stack<ListNode> iu=new Stack<>();
        ListNode cur =head;
        while(cur!=null){
            iu.push(cur);
            cur=cur.next;
        }
        ListNode Thead=new ListNode();
        cur=Thead;
        //弹出
        while(!iu.isEmpty()){
            cur.next=iu.pop();
            cur=cur.next;
        }
        cur.next=null;
        return Thead.next;
    }


    /*
    给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回null。
    如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
    为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表
    中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
    注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
    不允许修改 链表。
    https://leetcode.cn/problems/linked-list-cycle-ii
     */
    //这个解法是简单的解法,还可以用快慢指针来解决需要进行公式的推导
    public ListNode detectCycle(ListNode head) {
        //用集合来判断cur一直往后走如果集合包含了该元素说明这是第一个节点cur等于null时就说明没环
        Set<ListNode> iu=new HashSet<>();
        ListNode cur =head;
        while(cur!=null){
            if (!iu.contains(cur)){
                iu.add(cur);
            }else{
                return cur;
            }
            cur=cur.next;
        }
        return null;
    }
}